package com.c2b.algorithm.leetcode.base;

/**
 * @author c2b
 * @since 2023/11/22 15:49
 */
public class LC1080 {

    static class Solution {
        public TreeNode sufficientSubset(TreeNode root, int limit) {
            return checkSufficientLeaf(root, 0, limit) ? root : null;
        }

        private boolean checkSufficientLeaf(TreeNode currNode, int sum, int limit) {
            if (currNode == null) {
                return false;
            }
            if (currNode.left == null && currNode.right == null) {
                return currNode.val + sum >= limit;
            }
            // 检查左子树是否有足够的叶子
            boolean haveSufficientLeft = checkSufficientLeaf(currNode.left, sum + currNode.val, limit);
            // 检查右子树是否有足够的叶子
            boolean haveSufficientRight = checkSufficientLeaf(currNode.right, sum + currNode.val, limit);
            if (!haveSufficientLeft) {
                currNode.left = null;
            }
            if (!haveSufficientRight) {
                currNode.right = null;
            }
            return haveSufficientLeft || haveSufficientRight;
        }
    }

    public static void main(String[] args) {
        TreeNode root1 = new TreeNode(1);
        root1.left = new TreeNode(2);
        root1.left.left = new TreeNode(4);
        root1.left.left.left = new TreeNode(8);
        root1.left.left.right = new TreeNode(9);
        root1.left.right = new TreeNode(-99);
        root1.left.right.left = new TreeNode(-99);
        root1.left.right.right = new TreeNode(-99);
        root1.right = new TreeNode(3);
        root1.right.left = new TreeNode(-99);
        root1.right.left.left = new TreeNode(12);
        root1.right.left.right = new TreeNode(13);
        root1.right.right = new TreeNode(7);
        root1.right.right.left = new TreeNode(-99);
        root1.right.right.right = new TreeNode(14);

        Solution solution = new Solution();
        TreeNode.printTree(solution.sufficientSubset(root1, 1));

    }
}
